//Given n non-negative integers representing the histogram's bar height where th
//e width of each bar is 1, find the area of largest rectangle in the histogram. 
//
// 
//
// 
//Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3
//]. 
//
// 
//
// 
//The largest rectangle is shown in the shaded area, which has area = 10 unit. 
//
// 
//
// Example: 
//
// 
//Input: [2,1,5,6,2,3]
//Output: 10
// 
// Related Topics 栈 数组

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    // 栈：保留还未计算出来的 index
    fun largestRectangleArea(heights: IntArray): Int {
        var result = 0
        val stack = Stack<Int>()
        val list = ArrayList<Int>(heights.size + 2)
        list.add(0)
        list.addAll(heights.toTypedArray())
        list.add(0)
        stack.add(0)

        for (i in 1 until list.size) {
            while (list[stack.peek()] > list[i]) {
                val h = list[stack.pop()]
                val w = i - stack.peek() - 1
                result = java.lang.Math.max(h * w, result)
            }
            stack.push(i)
        }
        return result
    }
}
//leetcode submit region end(Prohibit modification and deletion)
